#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;

// a^k%p
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1)                 // 低位为1
            res = (LL)res * a % p; // 将该a次幂乘进去
        k >>= 1;                   // 左移
        a = (LL)a * a % p;         // 将a平方
    }
    return res;
}

int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, p;
        scanf("%d%d%d", &a, &p);
        int res = ("%d\n", qmi(a, p - 2, p)); // 快速幂求a的p-2次
        if (a % p)
            printf("%d\n", res);
        else
            puts("impossible"); // a是p的倍数一定无解（不可能mod为1）
    }
}